package com.exercises;


import com.alibaba.fastjson.JSONObject;

import java.util.HashMap;
import java.util.Map;


class Exercise1711 {
    public static void main(String[] args) {
        int[] a = new int[]{149, 107, 1, 63, 0, 1, 6867, 1325, 5611, 2581, 39, 89, 46, 18, 12, 20, 22, 234};
        int res = countPairs(a);
        System.out.println("===================");
        System.out.println(res);
    }

    public static int countPairs(int[] deliciousness) {
        final int MOD = 1000000007;
        int maxValue = 0;
        for (int i : deliciousness) {
            maxValue = Math.max(i, maxValue);
        }
        int maxSum = maxValue * 2;
        int result = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int length = deliciousness.length;
        for (int i = 0; i < length; i++) {
            int value = deliciousness[i];
            for (int sum = 1; sum <= maxSum; sum <<= 1) {
                int count = map.getOrDefault(sum - value, 0);
                result = (result + count) % MOD;
            }

            map.put(value, map.getOrDefault(value, 0) + 1);
        }
        return result;
    }

}

